package tree

import (
	"errors"
	"log"
)

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/
// 是否是镜像对称的
// 算法: 通过栈 遍历整个树
// 时间复杂度: O(n)
// 当前: 调试错误用例 [1,2,2,null,3,3] （WA）
func IsSymmetric(root *TreeNode) bool {
	if nil == root {
		return true
	}
	queue := NewQueue()
	queue.PushBack(root.Left)
	queue.PushBack(root.Right)
	for {
		isAllNil := true
		currentNodeNum := queue.Size()
		nextLevelLeftQueue := NewQueue()
		nextLevelRightQueue := NewQueue()
		for currentNodeNum > 0 {
			leftNodeObj, _ := queue.PopFront()
			rightNodeObj, _ := queue.PopBack()
			leftNode, leftOk := leftNodeObj.(*TreeNode)
			rightNode, rightOk := rightNodeObj.(*TreeNode)
			if leftOk && rightOk && nil != leftNode && nil != rightNode {
				log.Printf("left: %v, right: %v", leftNode, rightNode)
				if leftNode.Val != rightNode.Val {
					return false
				}
			} else if leftNode != rightNode {
				// 一旦有一侧元素获取为空，就一定要都为空，才算匹配
				return false
			}
			if nil != leftNode || nil != rightNode {
				isAllNil = false
			}
			if nil != leftNode {
				nextLevelLeftQueue.PushBack(leftNode.Left)
				nextLevelLeftQueue.PushBack(leftNode.Right)
			} else {
				nextLevelLeftQueue.PushBack(nil)
				nextLevelLeftQueue.PushBack(nil)
			}
			if nil != rightNode {
				nextLevelRightQueue.PushFront(rightNode.Right)
				nextLevelRightQueue.PushFront(rightNode.Left)
			} else {
				nextLevelRightQueue.PushFront(nil)
				nextLevelRightQueue.PushFront(nil)
			}
			currentNodeNum -= 2
		}
		if isAllNil {
			return true
		}
		nextLevelLeftQueue.Merge(nextLevelRightQueue)
		queue = nextLevelLeftQueue
		log.Printf("current queue size: %d", queue.Size())
	}
}

// 实现一个双向队列
type Queue struct {
	arr []interface{}
}

func (queue *Queue) Size() int {
	return len(queue.arr)
}

func (queue *Queue) PopBack() (interface{}, error) {
	if len(queue.arr) == 0 {
		return nil, errors.New("the stack is empty")
	}
	toPop := queue.arr[len(queue.arr)-1]
	queue.arr = queue.arr[:len(queue.arr)-1]
	return toPop, nil
}

func (queue *Queue) PushBack(i interface{}) {
	queue.arr = append(queue.arr, i)
}

func (queue *Queue) PopFront() (interface{}, error) {
	if len(queue.arr) == 0 {
		return nil, errors.New("the stack is empty")
	}
	toPop := queue.arr[0]
	queue.arr = queue.arr[1:]
	return toPop, nil
}

func (queue *Queue) PushFront(i interface{}) {
	queue.arr = append([]interface{}{i}, queue.arr...)
}

func (queue *Queue) Merge(rightQueue *Queue) {
	for rightQueue.Size() > 0 {
		currentEle, _ := rightQueue.PopFront()
		queue.PushBack(currentEle)
	}
}

func NewQueue() *Queue {
	queue := new(Queue)
	queue.arr = make([]interface{}, 0)
	return queue
}
